
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


public class BST {
    // 二叉树的创建。  根据完全二叉树的结构顺序进行创建。
    public static TreeNode creat(Integer[] nums){
        TreeNode root = new TreeNode(nums[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> queueIndex = new LinkedList<>();
        queue.offer(root);
        queueIndex.offer(1);
        while(!queue.isEmpty()){
            TreeNode p = queue.poll();
            int index = queueIndex.poll();
            if(index*2 <= nums.length && nums[index*2 - 1] != null){
                p.left = new TreeNode(nums[index * 2 - 1]);
                queue.offer(p.left);
                queueIndex.offer(index*2);
            }
            if(index * 2 + 1 <= nums.length && nums[index * 2] != null){
                p.right = new TreeNode(nums[index * 2]);
                queue.offer(p.right);
                queueIndex.offer(index*2+1);
            }
        }
        return root;
    }

    // 二叉树的中序遍历打印
    public static void myBSTPrint(TreeNode root){
        if(root == null){
            return;
        }
        myBSTPrint(root.left);
        System.out.print(root.val);
        System.out.print("\t");
        myBSTPrint(root.right);
    }

    // 二叉搜索树的查找。  递归实现
    public static TreeNode seek(TreeNode root, int val){
        if(root == null){
            return null;
        }
        if(root.val > val){
            return seek(root.left, val);
        }else if(root.val < val){
            return seek(root.right, val);
        }else{
            return root;
        }
    }

    // 二叉搜索树的插入,返回根节点
    public static TreeNode insert(TreeNode root, int val){
        return putNode(root,val);
    }
    public static TreeNode putNode(TreeNode root, int val){
        if(root == null){
            return new TreeNode(val);
        }
        if(root.val > val){
            root.left = putNode(root.left, val);
        }else if(root.val < val){
            root.right = putNode(root.right,val);
        }
        return root;
    }

    // 获取二叉查找树最大值
    public static TreeNode getMax(TreeNode root){
        if(root == null){
            return null;
        }
        if(root.right == null){
            return root;
        }else{
            return getMax(root.right);
        }
    }

    // 获得二叉查找树最小值
    public static TreeNode getMin(TreeNode root){
        if(root == null){
            return null;
        }
        return root.left == null ? root : getMin(root.left);
    }

    // ceiling 操作
    public static TreeNode getCeil(TreeNode root, double val){
        if(root == null){
            return null;
        }
        if(root.val < val){
            return getCeil(root.right,val);
        }else if(root.val == val){
            return root;
        }else{
            TreeNode left = getCeil(root.left, val);
            return  left == null ? root : left;
        }
    }

    // floor操作
    public static TreeNode getFloor(TreeNode root, double val){
        if(root == null){
            return null;
        }
        if(root.val > val){
            return getFloor(root.left,val);
        }else if(root.val == val){
            return root;
        }else{
            TreeNode right = getFloor(root.right,val);
            return right == null ? root : right;
        }
    }

    // 求树中节点个数
    public static int size(TreeNode root){
        if(root == null){
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }

    // 求树高
    public static int high(TreeNode root){
        if(root == null){
            return 0;
        }
        return Math.max(high(root.left),high(root.right)) + 1;
    }

    // 求排名为k的节点，从1开始数
    public static TreeNode find(TreeNode root, int k){
        if(root == null || k <= 0){
            return null;
        }
        int leftSize = size(root.left);
        if(leftSize > k - 1){
            return find(root.left,k);
        }else if(leftSize < k - 1){
            return find(root.right, k - leftSize - 1);
        }else{
            return root;
        }
    }

    // 求给定节点在树中的排名,从1开始，不存在该节点时返回插入后的排名
    public static int rank(TreeNode root, int val){
        if(root == null){
            return 1;
        }
        if(root.val > val){
            return rank(root.left,val);
        }else if(root.val < val){
            return rank(root.right,val)+size(root.left)+1;
        }else{
            return size(root.left) + 1;
        }
    }

    // 删除最大值
    public static TreeNode deleteMax(TreeNode root){
        if(root == null){
            return null;
        }
        if(root.right == null){
            return root.left;
        }else{
            root.right = deleteMax(root.right);
            return root;
        }
    }

    // 删除最小值
    public static TreeNode deleteMin(TreeNode root){
        if(root == null){
            return null;
        }
        if(root.left == null){
            return root.right;
        }else{
            root.left = deleteMin(root.left);
            return root;
        }
    }

    // 删除树中一个指定值，同时保证仍然是二叉排序树；不存在时则不删,返回根节点
    public static TreeNode delete(TreeNode root, int val){
        if(root == null){
            return null;
        }
        if(root.val < val){     // 在右子树中
            root.right = delete(root.right,val);
            return root;
        }else if(root.val > val){    // 在左子树中
            root.left = delete(root.left,val);
            return root;
        }else{             // 要删除的是根节点
            if(root.left == null){     // 左子树为空
                return root.right;
            }
            if(root.right == null){   // 右子树为空
                return root.left;
            }
            TreeNode temp = root;
            root = getMin(temp.right);     // 找到右子树中最小值，也就是root的后继结点
            root.right = deleteMin(temp.right);   // 删去右子树中最小的那个节点，然后连接到新的当前root的右子树上，此时的root就是删除的那个最小节点
            root.left = temp.left;        // 左子树归位，这一句必须在最后执行！！！   必须等右子树处理完毕再处理，否则，在删除右子树中最小值时就会出现错误！！！
            return root;     // 返回删除后得到的新的根节点
        }
    }


    // 实现范围查找，可以返回给定范围内的节点
    public static List<TreeNode> intervalSearch(TreeNode root, int min, int max){
        List<TreeNode> nodesList = new ArrayList<>();
        getNodes(root,min,max,nodesList);
        return nodesList;
    }

    public static void getNodes(TreeNode root, int min, int max, List<TreeNode> nodeList){
        if(root == null){
            return;
        }
        //  ============================第一种递归方式===============================================================
//        if(root.val < min){    // 符合要求的点都在右子树上
//            getNodes(root.right,min,max,nodeList);
//        }else if(root.val > max){  // 符合要求的点都在左子树上
//            getNodes(root.left,min,max,nodeList);
//        }else{      // 符合要求的点左右子树均可能有，根节点一定符合要求
//            nodeList.add(root);    // 添加根节点
//            getNodes(root.left,min,max,nodeList);    // 在左子树找
//            getNodes(root.right,min,max,nodeList);   // 在右子树找
//        }

   //====================================第二种递归方式============================================================
        if(root.val >= min && root.val <= max){    // 根节点位于范围内
            nodeList.add(root);
        }
        if(root.val > min){    // 左子树可能存在位于范围内的点
            getNodes(root.left,min,max,nodeList);
        }
        if(root.val < max){    // 右子树可能存在位于范围内的点
            getNodes(root.right, min, max, nodeList);
        }
    }

}
